Data stored on magnetic media, such as a magnetic disks, are typically stored in encoded form, so that errors in the stored data can possibly be corrected. The errors may occur, for example, because of inter-symbol interference, a defect in the disk, or noise. As the density of the data stored on the disk increases, more errors are likely, and the system is required to correct greater numbers of errors, which include greater numbers of burst errors. A burst error is typically defined as a contiguous number of symbols in which the first symbol and the last symbol are erroneous. The speed with which the system corrects the errors, including the burst errors, is important to the overall speed with which the system processes the data.
Prior to recording, multiple-bit data symbols are encoded using an error correction code (ECC). When the data symbols are retrieved from the disk and demodulated, the ECC is employed to, as the name implies, correct the erroneous data.
Specifically, before a string of k data symbols is written to a disk, it is mathematically encoded using an (n, k) ECC to form n-k ECC symbols. The ECC symbols are then appended to the data string to form an n-symbol error correction code word, which is then written to, or stored, on the disk. When the data are read from the disk, the code words containing the data symbols and ECC symbols are retrieved and mathematically decoded. During decoding, errors in the data are detected and, if possible, corrected through manipulation of the ECC symbols [for a detailed description of decoding see, Peterson and Weldon, Error Correction Codes, 2nd Ed. MIT Press. 1972].
To correct multiple errors in strings of data symbols, the system typically uses an ECC that efficiently and effectively utilizes the various mathematical properties of sets of symbols known as Galois fields. Galois fields are represented "GF (P.sup.M)", where "P" is a prime number and "M" can be thought of as the number of digits, base "P", in each element or symbol in the field. P usually has the value 2 in digital computer and disk drive applications and, therefore, M is the number of bits in each symbol. The ECC's commonly used with the Galois Fields are Reed Solomon codes or BCH codes.
Reed Solomon and BCH encoding and decoding operations involve a plurality of Galois field multiplication operations. The Galois field multiplication operations are modulo g(x), which is the generator polynomial of the Galois field. The modulo g(x) operation, also denoted mod g(x), for g(x)=g.sub.n x.sup.n +g.sub.n-1 x.sup.n-1 + . . . +g.sub.1 x+g.sub.0 is defined as p(x) mod g(x)=r(x), where r(x) is the remainder of p(x) divided by g(x). Accordingly, EQU x.sup.i mod g(x)=x, for i&lt;n EQU x.sup.n mod g(x)=g.sub.n-1 x.sup.n- +g.sub.n-2 x.sup.n-2 + . . . +g.sub.1 x+g.sub.0 EQU x.sup.n+1 mod g(x)=g.sub.n-1 x.sup.n-1 +g.sub.n-2 x.sup.n-2 + . . . g.sub.1 x+g.sub.0)+g.sub.n-2 x.sup.n-1 +g.sub.n-3 x.sup.n-2 + . . . +g.sub.1 x.sup.2 +g.sub.0 x EQU x.sup.n+j mod g(x)=d.sub.j,.sub.n-1 x.sup.n-1 +d.sub.j,.sub.n-2 x.sup.n-2 + . . . d.sub.j,.sub.1 x+d.sub.j,.sub.0
The conventional Galois field multiplication operation over GF(2.sup.n) involves three steps: multiplying two degree-(n-1) polynomials a(x) and b(x) together bit-by-bit to produce a degree-(2n-2) polynomial c(x); mapping the x.sup.2n-2, x.sup.2n-3, . . . x.sup.n terms of c(x) to: ##EQU1## and exclusive-OR'ing the terms of the summation to the x.sup.n-1, x.sup.n-2, . . . x.sup.0 terms of c(x). This conventional method involves, in the first step, 2n-1 bit computations to produce the degree-(2n-2) polynomial and, in the second step, a complicated mapping scheme. For example, Galois field multiplication over GF(2.sup.8), with g(x)=x.sup.8 +x.sup.4 +x.sup.3 +x.sup.2 +1 includes the relatively complicated mapping of the sequence c.sub.14, c.sub.13 . . . c.sub.8 to the sequence c.sub.11 +c.sub.12 +c.sub.13, c.sub.10 +c.sub.11 +c.sub.12, c.sub.9 +c.sub.10 +c.sub.11, c.sub.8 +c.sub.9 +c.sub.10 +c.sub.14, c.sub.8 +c.sub.9 +c.sub.11 +c.sub.12, c.sub.8 +c.sub.10 +c.sub.12 +c.sub.13, c.sub.9 +c.sub.13 c.sub.14, c.sub.8 +c.sub.12 +c.sub.13. For larger Galois fields the mapping is even more complicated.
One known prior system avoids the complicated mapping by performing sequential modulo g(x) operations. Such a system uses the results of a previous x.sup.i b(x) mod g(x) computation to determine x.sup.i+1 b(x) mod g(x)=x[x.sup.i b(x) mod g(x)]mod g(x). The iteration involves one shift and one exclusive-OR operation of two n-bit symbols. While each iteration is straight forward, the entire operation is slow, particularly for larger Galois fields, because of the number of iterations that must be performed.
Larger Galois fields, that is, fields larger than GF(2.sup.8) are being used more and more as the density of the data increases. The larger fields are necessary to produce the longer data codewords that are required to protect the data. Consequently, Galois field multiplication operations over the larger fields must be performed to both encode and decode the data codewords. What is needed is a Galois field multiplier that is less complex than the conventional Galois field multipliers, and produces the product relatively quickly.